package com.fwzhang.third.collectionframework.collection.list;

import java.io.Serializable;
import java.util.*;
import java.util.function.Predicate;

/**
 * vector
 */
public class VectorClass<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {

    /**
     * Vector 线程安全的List集合
     * 通过数组存储数据
     * 通过 <p>synchronized</p> 修饰符保证线程安全
     * 由于synchronized为重度锁，会造成list集合操作效率低
     * 在Vector类中，一旦方法的结果可能会因为其他线程对当前Vector对象操作造成结果与预期不同
     *  该方法都会被synchronized修饰
     *
     * Vector的迭代器中，迭代方法都在方法内部使用了synchronized
     *
     * Vector中方法的逻辑与ArrayList基本一致，只不过多了synchronized修饰
     */

    protected Object[] elementData;

    /**
     * 相当于size
     *
     * @serial
     */
    protected int elementCount;

    /**
     * 需要扩展的容量大小
     * @serial
     */
    protected int capacityIncrement;

    /**
     * {@inheritDoc}
     *
     * @param index
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public synchronized E get(int index) {
        return (E) elementData[index];
    }

    @Override
    public synchronized int size() {
        return elementCount;
    }

    /**
     * 删除符合条件的element
     * Vector类中该方法的整体思路
     *  1、确定数组中符合条件的节点
     *  2、删除符合条件的节点
     * 整体思路与ArrayList中的方法一致
     * @since 1.8
     */
    @Override
    public synchronized boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final int size = elementCount;
        // 通过位图记录集合中哪个索引位置的元素需要删除
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        // 如果第一次遍历过程中计算的道德删除的个数大于0，则代表存在需要删除的元素
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                // i 代表不需要删除的元素的索引
                // https://blog.csdn.net/PrimeYun/article/details/100146636
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            elementCount = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }
}
